﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;

using Util;

namespace Algorithm.Sort
{
    /// <summary>
    /// Insertion sort is a simple sorting algorithm: 
    /// a comparison sort in which the sorted array (or list) is built one entry at a time. 
    /// It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
    /// However, insertion sort provides several advantages:
    /// 1. Simple implementation
    /// 2. Efficient for (quite) small data sets
    /// 3. Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d),
    ///    where d is the number of inversions
    /// 4. More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or 
    ///    bubble sort; the best case (nearly sorted input) is O(n)
    /// 5. Stable; i.e., does not change the relative order of elements with equal keys
    /// 6. In-place; i.e., only requires a constant amount O(1) of additional memory space
    /// 7. Online; i.e., can sort a list as it receives it
    /// When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class InsertionSorter <T> : SorterBase<T>
    {
        [AlgorithmVariation]
        private static void InsertionSort(T[] list, IComparer<T> comparer)
        {
            // The index of insertion destination.
            int j;

            // The element to be inserted.
            T temp;

            // Inserts each element into the ordered list by index i.
            for (int i = 0; i < list.Length; i++)
            {
                // Scans the list from i to the head, inserts list[i] to the final position indicated by j.
                j = i;

                temp = list[i];

                while (j > 0 && comparer.Compare(list[j - 1], temp) > 0)
                {
                    // Shifts element to one position right.
                    list[j] = list[j - 1];
                    j--;
                }

                // Founds the index of destination and put the element.
                list[j] = temp;
            }
        }
    }
}
